package common.test;

import common.TreeNode;

/**
 * 437. 路径总和 III
 */
public class _437_PathSum {

    int ans = 0;

    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        pathSum2(root, targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ans;
    }

    public void pathSum2(TreeNode root, long targetSum) {
        if (root == null) {
            return;
        }
        if (targetSum == root.val) {
            ans++;
        }
        pathSum2(root.left, targetSum - root.val);
        pathSum2(root.right, targetSum - root.val);
    }
}
